|
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of rewriting systems. In its simplest form, an ARS is simply a set (of "objects") together with a binary relation, traditionally denoted with ; this definition can be further refined if we index (label) subsets of the binary relation. Despite its simplicity, an ARS is sufficient to describe important properties of rewriting systems like normal forms, termination, and various notions of confluence. Historically, there have been several formalizations of rewriting in an abstract setting, each with its idiosyncrasies. This is due in part to the fact that some notions are equivalent, see below in this article. The formalization that is most commonly encountered in monographs and textbooks, and which is generally followed here, is due to Gérard Huet (1980).〔Book and Otto, p. 9〕 == Definition == Abstract reduction system, (abbreviated ARS) is the most general (unidimensional) notion about specifying a set of objects and rules that can be applied to transform them. More recently authors use abstract rewriting system as well.〔Terese, p. 7,〕 (The preference for the word "reduction" here instead of "rewriting" constitutes a departure from the uniform use of "rewriting" in the names of systems that are particularizations of ARS. Because the word "reduction" does not appear in the names of more specialized systems, in older texts reduction system is a synonym for ARS).〔Book and Otto, p. 10〕 An ARS is a set ''A'', whose elements are usually called objects, together with a binary relation on ''A'', traditionally denoted by →, and called the reduction relation, rewrite relation〔Terese, p. 7〕 or just reduction.〔Book and Otto, p. 10〕 This (entrenched) terminology using "reduction" is a little misleading, because the relation is not necessarily reducing some measure of the objects. In some contexts it may be beneficial to distinguish between some subsets of the rules, i.e. some subsets of the reduction relation →, e.g. the entire reduction relation may consist of associativity and commutativity rules. Consequently, some authors define the reduction relation → as the indexed union of some relations; for instance if , the notation used is (A, →1, →2). As a mathematical object, an ARS is exactly the same as an unlabeled state transition system, and if the relation is considered as an indexed union, then an ARS is the same as a labeled state transition system with the indices being the labels. The focus of the study, and the terminology are different however. In a state transition system one is interested in interpreting the labels as actions, whereas in an ARS the focus is on how objects may be transformed (rewritten) into others.〔Terese, p. 7-8〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Abstract rewriting system」の詳細全文を読む スポンサード リンク
|